Now that we've seen how diverse applications can be modeled as connected networks, let's formalize the core components we'll be working with. Understanding this graph theory terminology is crucial for discussing and implementing MST algorithms.

  • Vertex (or Node): A fundamental unit of the graph, representing an object. In our example, $A, B, C, D, E, F$ are the vertices.
  • Edge (or Link): A connection between two vertices. An edge from $u$ to $v$ with weight $w$ is written as $(u, v, w)$. For instance, $(A, B, 4)$ is an edge.
  • Weighted Graph: A graph where each edge has an associated numerical value, or weight, representing a cost, distance, or capacity. Our example is a weighted graph.
  • Undirected Graph: A graph where edges have no inherent direction. A connection from vertex $A$ to $B$ is identical to a connection from $B$ to $A$. All MST algorithms operate on undirected graphs.
  • Connected Graph: A graph where a path exists between any two vertices. There are no isolated sections, which is a necessary precondition for creating a spanning tree.

Graph $G$

A graph $G$ is formally defined as an ordered pair $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges. For a weighted, undirected graph, each edge in $E$ connects a pair of vertices $\{u, v\}$ from $V$ and has an associated weight $w(u, v)$.